121 Best Time to Buy and Sell Stock

• 給定一組股票價格 prices[i]，i 代表第 i 天的價格，你只能在某一天買入並在之後的某一天賣出，求最大獲利（如果無法獲利，回傳 0）。
• Kotlin, O(n) Greedy

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0
    for (price in prices) {
        if (price < minPrice) {
            minPrice = price
        } else {
            maxProfit = maxOf(maxProfit, price - minPrice)
        }
    }
    return maxProfit
}

• follow up
  • 如果允許多次買賣（不必等前一次賣出才能買入），該怎麼改？（LeetCode 122）
  • 如果只能進行兩次交易呢？（LeetCode 123）
  • 如果有交易費用或冷卻期要怎麼處理？（LeetCode 714, 309）
  • 為什麼這裡用 greedy 就可以解，而不是 DP？